#ifndef SKIP_LIST_DEF_HPP
#define SKIP_LIST_DEF_HPP

#include <algorithm.hpp>
#include <allocator.hpp>
#include <array.hpp>
#include <iterator.hpp>
#include <stdio.h>
/**
 * 跳表
 *
 */

#define DEF_SKIP_LIST_Height 16 // 跳表默认高度
#define SKIP_LIST_MIN 8

template <typename T, size_t Height>
struct SkipListBaseNode;
template <typename T, size_t Height>
struct SKipListNode;

template <typename T, size_t Height>
struct SkipListBaseNode {
    static_assert(Height >= SKIP_LIST_MIN,
                  "SkipList Height must greater than 8");
    using basePtr = SkipListBaseNode<T, Height> *;
    using nodePtr = SKipListNode<T, Height> *;
    basePtr next[Height];

    inline nodePtr castNodePtr() {
        return static_cast<nodePtr>(&*this);
    }

    void linkSelf() {
        for (auto i = 0; i < Height; ++i) {
            next[i] = &*this;
        }
    }

    void swap(SkipListBaseNode &other) {
        nodePtr temp;
        for (auto i = 0; i < Height; ++i) {
            temp = next[i];
            next[i] = other.next[i];
            other.next[i] = next[i];
        }
    }
};

template <typename T, size_t Height>
struct SKipListNode : public SkipListBaseNode<T, Height> {
    T value;

    void swap(SKipListNode &other) {
        SkipListBaseNode::swap(other);
        std::swap(value, other.value);
    }
};

template <typename T, size_t Height>
class SkipListIterator
    : public TingSTL::base_iterator<TingSTL::forward_iterator_tag, T> {
public:
    using basePtr = typename SkipListBaseNode<T, Height>::basePtr;

private:
    basePtr _node = nullptr;

public:
    SkipListIterator() = default;

    SkipListIterator(basePtr node) {
        _node = node;
    }

    SkipListIterator &operator++() {
        _node = _node->next[0];
        return *this;
    }

    SkipListIterator &operator++(int) {
        auto temp = _node;
        _node = _node->next[0];
        return {temp};
    }

    SkipListIterator &operator+(difference_type n) {
        for (; n > 0; --n) {
            _node = _node->next[0];
        }
        return *this;
    }

    bool operator!=(const SkipListIterator &other) {
        return _node != other._node;
    }

    T &operator*() {
        return _node->castNodePtr()->value;
    }
};

/**
 * @brief SkipList 跳表
 * 每一层都是 不带头结点的单向链表
 * @tparam T
 * @tparam Compare 比较器
 * @tparam Alloc
 */
template <typename T, typename Compare = TingSTL::less<T>,
          size_t Height = DEF_SKIP_LIST_Height,
          typename Alloc = TingSTL::allocator<T>>
class SkipList {
public:
    using node = typename SKipListNode<T, Height>;
    using baseNode = typename SkipListBaseNode<T, Height>;
    using basePtr = typename baseNode::basePtr;
    using nodePtr = typename baseNode::nodePtr;
    using dataAlloc = typename Alloc;
    using nodeAlloc = typename TingSTL::rebind_alloc_t<Alloc, node>;
    using baseAlloc = typename TingSTL::rebind_alloc_t<Alloc, baseNode>;
    using typeAlloc = typename Alloc;
    using nodePtr = typename node::nodePtr;
    using compare = typename Compare;
    using iterator = SkipListIterator<T, Height>;
    using const_iterator = const SkipListIterator<T, Height>;
    static constexpr const size_t SkipListHeight = Height;

private:
    size_t _size;
    basePtr _head; // 数据node, 每一层不带头结点且
    compare _comp; // 比较器
public:
    SkipList() :
        _size(0), _comp() {
        _head = baseAlloc::allocate(1);
        for (size_t i = 0; i < Height; ++i) {
            _head->next[i] = _head;
        }
    }

    ~SkipList() {
        clear();
        baseAlloc::deallocate(_head);
        _head = nullptr;
    }

    SkipList(const SkipList &other) {
        // TODO:
    }

    SkipList(SkipList &&other) {
        _head = other._head;
        _size = other._size;
        _comp = std::move(other._camp);
    }

    SkipList &operator=(SkipList other) {
        swap(other);
        return *this;
    }

    void swap(SkipList &other) {
        std::swap(_size, other._size);
        std::swap(_head, other._head);
    }

    // //////////////////// 添加移除数据 ////////////////////

    // 添加新数据 允许重复添加
    void add(const T &v) {
        auto path = indexPath(v);
        auto node = createNode(v);
        for (auto i = 0; i < Height; ++i) {
            // 插入节点
            linkAtPosBack(path[i], node, i);
            // 50% 的概率建立索引结点
            if (rand() % 2 == 0)
                break;
            // std::cout << "link height: " << i << "\n";
        }

        ++_size;
    }

    // 返回删除之后的位置
    iterator erase(const T &v) {
        auto path = indexPath(v);
        auto node = path[0]->next[0];

        if (node == _head || _comp(v, node->castNodePtr()->value))
            return {_head};

        // 如果 原始链表存在数据，这个链表中就存在该数据,断开该节点, 连接到 node后面的节点
        for (auto i = 0; i < Height && path[i]->next[i] == node; ++i) {
            path[i]->next[i] = node->next[i];
        }

        auto pos = node->next[0];
        destroyNode(node->castNodePtr());
        return {pos};
    }

    iterator find(const T &target) {
        auto p = _head;
        for (int i = Height - 1; i >= 0; --i) {
            // 找到一层中 ， 小于target 最大结点
            while (p->next[i] != _head && _comp(p->next[i]->castNodePtr()->value, target)) {
                p = p->next[i];
            }
        }
        p = p->next[0];
        if (p != _head && !_comp(target, p->castNodePtr()->value))
            return {p};
        return {_head};
    }

    // ////////////////////  容量迭代器相关 ////////////////////
    inline bool empty() const {
        return _size == 0;
    }

    inline size_t size() const {
        return _size;
    }

    void clear() {
        auto curNode = _head->next[0];
        decltype(curNode) next = nullptr;
        while (curNode != _head) {
            next = curNode->next[0];
            destroyNode(curNode->castNodePtr());
            curNode = next;
        }
        _head->linkSelf();
        _size = 0;
    }

    inline iterator begin() noexcept {
        return {_head->next[0]};
    }

    inline iterator end() noexcept {
        return {_head};
    }

    inline iterator begin() const noexcept {
        return {_head->next[0]};
    }

    inline iterator end() const noexcept {
        return {_head};
    }

    inline const_iterator cbegin() const noexcept {
        return {_head->next[0]};
    }

    inline const_iterator cend() const noexcept {
        return {_head};
    }

    // //////////////////////////////// 调试相关 ////////////////////////////////

    /**
     * @brief 输出索引
     */
    void printIndex() const {
        for (int i = Height - 1; i >= 0; --i) {
            std::cout << "index [" << i << "] :";
            auto p = _head->next[i];
            while (p != _head) {
                std::cout << p->castNodePtr()->value << "->";
                p = p->next[i];
            }
            std::cout << "\n";
        }
    }

private:
    // //////////////////////////////// 链表组织 ////////////////////////////////
    inline void linkAtPosBack(basePtr pos, basePtr linkNode, size_t level) {
        linkNode->next[level] = pos->next[level];
        pos->next[level] = linkNode;
    }

    // 得到索引到数据结点的路径
    TingSTL::array<basePtr> indexPath(const T &target) {
        TingSTL::array<basePtr> path(Height, _head);
        auto p = _head;
        for (int i = Height - 1; i >= 0; --i) {
            // 找到一层中 ， 小于target 最大结点
            while (p->next[i] != _head && _comp(p->next[i]->castNodePtr()->value, target)) {
                p = p->next[i];
            }
            // 这一层遍历完成，遍历下一层索引
            path[i] = p;
        }
        // for (int i = Height - 1; i >= 0; --i) {
        //     std::cout << "path" << i << ": ";
        //     if (path[i] != _head)
        //         std::cout << path[i]->castNodePtr()->value;
        //     std::cout << "\n";
        // }
        return path;
    }

    // /////////////////////////////// 内存管理 ////////////////////////////////
    template <typename... Args>
    nodePtr createNode(Args &&...args) {
        auto ret = nodeAlloc::allocate(1);
        try {
            typeAlloc::construct(&ret->value, std::forward<Args>(args)...);
        } catch (...) {
            nodeAlloc::deallocate(ret);
            throw;
        }
        for (auto i = 0; i < Height; ++i) {
            ret->next[i] = _head;
        }
        return ret;
    }

    void destroyNode(nodePtr node) {
        typeAlloc::destroy(&node->value);
        nodeAlloc::deallocate(node);
    }
};

#endif // SKIP_LIST_DEF_HPP